package version2024.medium;

import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ75 公共子串计算  动态规划
 * @Date: created in 2025/1/7 星期二 15:27
 * @Modified By:
 */
public class HJ75_PublicSubstringCalculation {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.next();
            String b = in.next();

            //       b c d e
            //     0 1 2 3 4
            //   0 0 0 0 0 0
            // a 1 0 0 0 0 0
            // b 2 0 1 0 0 0
            // c 3 0 0 2 0 0
            // f 4 0 0 0 0 0
            // b 5 0 1 0 0 0
            // c 6 0 0 2 0 0
            // d 7 0 0 0 3 0
            // e 8 0 0 0 0 4
            // f 9 0 0 0 0 0

            System.out.println(longString(a, b));
        }
    }

    public static int longString(String a, String b) {
        String shorter = null;
        String longer = null;
        if (a.length() > b.length()) {
            longer = a;
            shorter = b;
        } else {
            longer = b;
            shorter = a;
        }

        // dp数组的定义: 表示在较短字符串str1以第i个字符结尾，
        // str2中以第j个字符结尾时的公共子串长度。
        // baseCase就是0, 即没有公共子串时长度为0
        int[][] dp = new int[shorter.length() + 1][longer.length() + 1];

        int max = 0;
        for (int i = 1; i <= shorter.length(); i++) {
            for (int j = 1; j <= longer.length(); j++) {
                if (shorter.charAt(i - 1) == longer.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                    }
                } else {
                    // 两字符不同时, dp[i][j] 保持为0, 表示没有公共子串
                    dp[i][j] = 0;
                }
            }
        }

        return max;
    }
}
